Methods for coding an information signal form the basis for a significant amount of speech, audio, image and video transmissions through communication channels or from storage devices. Digital speech encoding standards for code division multiple access (CDMA) mobile phone systems, for example, are described in the approved specification (ANSI/TIA/EIA-95-B-1999) entitled “Mobile Station—Base Station Compatibility Standard for Wideband Spread Spectrum Cellular Systems” (1999), published by the Electronic Industries Association (EIA), 2500 Wilson Blvd., Arlington, Va., 22201. A variable rate speech codec, and specifically a Code Excited Linear Prediction (CELP) codec for use in communication systems compatible with IS-95, is defined in the document (TIA/EIA/IS-127) entitled “Enhanced Variable Rate Codec, Speech Service Option 3 for Wideband Spread Spectrum Digital Systems” (1997), published by the Electronics Industries Association (EIA), 2500 Wilson Blvd., Arlington, Va., 22201.
A method for encoding a speech signal using factorial packing (FP) is described in “Factorial Packing Method and Apparatus for Information Coding”, U.S. Pat. No. 6,236,960 by Peng et al., issued May 22, 2001. This speech coder utilizes four characteristics to uniquely describe any given pulse combination: number of degenerate pulses, signs of pulses, positions of non-zero pulses, and pulse magnitudes. A four-stage iterative classification of the pulse combination is performed, starting with the number of non-zero pulses and then determining the remaining parameters. The most significant bits in FP have most of the information about the number of non-zero pulses, while the least significant bits have primarily sign information showing a partial segregation of constituent information in FP. There is no complete segregation in this method, and therefore an error in the central bits does not always ensure that the number of degenerate pulses can be decoded correctly.
The pyramid vector quantization (PVQ) method, as described by Fischer, “A Pyramid Vector Quantizer”, IEEE Transactions on Information Theory, Vol. IT-32, July 1986, pp. 568-583, is an example of an enumeration method. The enumeration technique may be very sensitive to bit errors. Hung et al., in the article “Error-Resilient Pyramid Vector Quantization for Image Compression”, IEEE Transactions on Image Processing, Vol. 7, October 1998, pp. 1373-1386, proposed some PVQ enumeration methods that are less sensitive to bit errors than those proposed by Fischer. Two of their proposed enumeration methods, Conditional Product Code (CPC) and Conditional Product-Product Code (CPPC), were found to be robust to bit errors when used for representing Discrete Cosine Transform (DCT) coefficients in image compression. FP may be considered a variant of CPC. FP and CPC achieve robust performance by “partial segregation” of information present in a pulse configuration. The CPPC method has more segregation of constituent information, although it also does not ensure complete segregation. The comparisons between CPPC and CPC indicate that the CPPC method may be more robust to bit errors, suggesting that increasing information segregation may increase robustness. With complete information segregation, none of the bits in the codeword is affected by more than one of the constituents. It would be preferred that addition and multiplication functions would not be used to combine constituent codewords into a complete codeword, as these operations may add to the complexity of the coding process, and also tend to decrease segregation. The codeword should be formed by a concatenation of the constituent codewords, thus maintaining complete information segregation for higher error resilience.
A method for coding an information signal based on parameters inherent to the information signal is described in “Method and Apparatus for Coding an Information Signal”, U.S. Pat. No. 6,141,638, W. Peng and J. Ashley, issued Oct. 31, 2000. The method selects one of a plurality of configurations based on predetermined parameters related to the information signal, each of the plurality of configurations having a codebook; and searches the codebook over the length of an excitation vector which is shorter than a sub-frame length, to determine a codebook index from the codebook corresponding to the selected configuration; and transmits the predetermined parameters and the codebook index to a destination.
A code-excited linear prediction (CELP) technique is described in the paper by James P. Ashley, Edgardo M. Cruz-Zeno, Udar Mittal and Weimen Peng, “Wideband Coding of Speech Using a Scalable Pulse Codebook”, Proceedings IEEE Workshop on Speech Coding 2000, Lake Delavan, Wis., September, 2000. The technique is scalable to a wide range of bit rates. The method improves the coding efficiency of multiple pulse ACELP tracks in wideband speech coding. The method was also shown to be extendable beyond Algebraic Code-Excited Linear Predictive (ACELP) speech coders, such that the standard track constraints are eliminated while still achieving high quality speech.
A method for coding “unconstrained” fixed codebook (FCB) excitation for ACELP speech coders is described in the paper by Udar Mittal, James P. Ashley and Edgardo M. Cruz-Zeno, “Coding Unconstrained FCB Excitation Using Combinatorial and Huffman Codes”, Proceedings IEEE Workshop on Speech Coding, October 2002. The unconstrained FCB does no place track-based constraints on the pulse positions. The coding method combines Huffman codes and combinational codes. The method is less sensitive to bit errors and is nearly as efficient as the combinational codes. The method includes efficiently storing the parameters in the combinational codebook.
Methods such as Pyramid Vector Quantization (PVQ) and Huffman Coded Factorial Packing (HCFP) are prior art techniques remove the multiply and divide operations during the formation of a codeword during encoding for representing the fixed codebook (FCB) excitation. In one aspect, the methods concern the formation of codeword for representing the FCB excitation having reduced bit error sensitivity. These methods reveal that removing the multiply and divide operations can result in a codeword having bit segregation property with less computational complexity and improved bit error sensitivity. For example, a single shift operation in PVQ can be used instead of a multiply operation. The operative aspects of PVQ and HCFP can improve the bit error robustness at an expense of using 1 or 2 bits more than the minimum bits required to form the codeword for the fixed codebook excitation. However, these methods do not address combination of constituent codewords belonging to a set such that the constituent codewords can be uniquely decoded from the combined codeword.
The prior art methods for efficient coding can include either combinational techniques or concatenation techniques. A combinational coding technique can combine and decombine two or more long codewords to form a combined codeword which generally involves a multi-precision multiply and/or divide operation. The multi-precision operations can be computationally demanding with excess precision and can result in high-bit error sensitive combined codewords. A concatenation method can append two or more long codewords together to form a combined codeword which generally does not require multiply and divide operations. However, the concatenation technique generally requires more bits than the combinational technique and is not as efficient with regard to the number of bits required to represent the combined codeword.
It is an object of this invention, therefore, to improve upon the computational complexity of combinational and concatenation coding and decoding, to provide higher efficiency and error resiliency associated with factorial packing methods and Huffman coding factorial packing methods, and to overcome the deficiencies and obstacles described above.